#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// https://leetcode.cn/problems/max-submatrix-lcci/description/
// 面试题 17.24. 最大子矩阵

class Solution
{
public:
    int maxSumArrOfSon(vector<int> &nums, int &begin, int &end)
    {
        int preIndex = 0;
        int ans = INT_MIN;
        int preSum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] + preSum >= nums[i])
            {
                preSum += nums[i];
            }
            else
            {
                // 更新
                preIndex = i;
                preSum = nums[i];
            }

            // 计数
            if (preSum > ans)
            {
                begin = preIndex;
                end = i;
                ans = preSum;
            }
        }
        return ans;
    }

    vector<int> getMaxMatrix(vector<vector<int>> &matrix)
    {
        vector<int> ans(4);

        vector<int> curSum;
        int begin = 0;
        int end = 0;

        int curMaxSum = INT_MIN;
        int row = matrix.size();
        int col = matrix[0].size();

        for (int i = 0; i < row; i++)
        {
            curSum = matrix[i];
            // 求最大连续和
            int temp = maxSumArrOfSon(curSum, begin, end);
            if (temp > curMaxSum)
            {
                ans[0] = i;
                ans[1] = begin;
                ans[2] = i;
                ans[3] = end;
                curMaxSum = temp;
            }
            for (int j = i + 1; j < row; j++)
            {
                // 将一个vector加到另一个vector上
                transform(curSum.begin(), curSum.end(), matrix[j].begin(), curSum.begin(),
                          [](int x, int y)
                          { return x + y; });
                int temp = maxSumArrOfSon(curSum, begin, end);
                if (temp > curMaxSum)
                {
                    ans[0] = i;
                    ans[1] = begin;
                    ans[2] = j;
                    ans[3] = end;
                    curMaxSum = temp;
                }
            }
        }
        return ans;
    }
};

int main()
{
    Solution solution{};
    vector<vector<int>> nums{{-1, 0}, {0, -1}};
    solution.getMaxMatrix(nums);
    return 0;
}